package com.cat.greedyAlgorithm;

import java.util.Arrays;
import java.util.Map;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-sideway-jumps/
 * @create 2025/9/1 11:34
 * @since JDK17
 */

public class Solution41 {
    public int minSideJumps(int[] obstacles) {
        int n = obstacles.length;
        int[][] dp = new int[n][3];
        dp[0][1] = 0;
        dp[0][0] = dp[0][2] = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {   // 当前位置是石头
                if (obstacles[i] == j + 1) {
                    dp[i][j] = Integer.MAX_VALUE;
                    continue;
                }
                int min = Integer.MAX_VALUE;
                for (int k = 0; k < 3; k++) {
                    if (obstacles[i - 1] == k + 1) {
                        continue;
                    }
                    min = Math.min(min, dp[i - 1][k] + (k != j ? 1 : 0) + (obstacles[i] == k + 1 ? 1 : 0));
                }
                dp[i][j] = min;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        return Arrays.stream(dp[n - 1]).min().getAsInt();
    }
}
